package com.zlk.algorithm.huawei.leetcode.dp.multidimensional;

import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName Code04_LongestPalindromicSubsequence
 * @description:todo
 * @author: slfang
 * @create: 2025-01-20 08:59
 * @Version 1.0
 **/
public class Code04_LongestPalindromicSubsequence {
    // 最长回文子序列
// 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度
// 测试链接 : https://leetcode.cn/problems/longest-palindromic-subsequence/


    // todo
    // text 分为原串和逆序串  s1,s2
    // dp[i][j] 标识从i,j位置出发的最大回文字串长度
    // dp[i][j]
    //    s1.charAt(i)==s2.charAt(j) : = dp[i+1][j+1]+1
    //                !=             : int p1 = f(s1,s2,i+1,j+1);
    //        int p2 = Math.max(f(s1,s2,i+1,j),f(s1,s2,i,j+1));
    //        return Math.max(p1,p2);
    public int longestPalindromeSubseq(String text) {
        String s1 = text;
        String s2 ="";
        int n = text.length();
        for (int i = n-1; i >=0 ; i--) {
            s2+=text.charAt(i);
        }
        int[] dp = new int[n+1];
        for (int i = n-1; i >=0 ; i--) {
            int rightDown = 0;
            for (int j = n-1; j >=0 ; j--) {
                int temp = dp[j];
                if(s1.charAt(i)==s2.charAt(j)){
                    dp[j] = rightDown+1;
                }else{
                    dp[j] = Math.max(Math.max(dp[j],dp[j+1]),rightDown);
                }
                rightDown = temp;
            }
        }
        return dp[0];
    }

    //1 <= s.length <= 1000
    public int longestPalindromeSubseq1(String text) {
        String s1 = text;
        String s2 ="";
        int n = text.length();
        for (int i = n-1; i >=0 ; i--) {
            s2+=text.charAt(i);
        }
        // a b c b a a
        // a a b c b a
        // dp[i][j]  原字符i位置与逆序字符j位置
        return f(s1,s2,0,0);
    }

    private int f(String s1, String s2, int i, int j) {
        //base case
        if(i==s1.length()||j==s2.length()){
            return 0;
        }
        if(s1.charAt(i)==s2.charAt(j)){
            return f(s1,s2,i+1,j+1)+1;
        }
        int p1 = f(s1,s2,i+1,j+1);
        int p2 = Math.max(f(s1,s2,i+1,j),f(s1,s2,i,j+1));
        return Math.max(p1,p2);
    }

    @Test
    public void test(){
        System.out.println(longestPalindromeSubseq1("bbbab"));
    }
}
